1. Field of Invention
The present invention generally concerns a method and apparatus for buffering and processing data packets within stations of a communications network in order to perform the communication protocol(s) required by given communication network, and more particularly to a single high speed data communication processing chip having multiple central processing units (i.e. CPUs), multiple data paths and means for internally separating and processing data packets associated with one layer of the communication protocol, while transferring data packets associated with other layers of the communication protocol to the host system.
2. Brief Description of the Prior Art
Local-area networks (LAN) are communication systems for enabling data-processing devices, such as computer workstations, to communicate with each other through a communication (e.g. transmission) media. Data-processing devices in such networks are typically referred to as nodes or stations, many such stations are likely to be relatively autonomous, requiring communication with other stations only occasionally. Other stations may require more frequent communication, and the amount of communication required by a particular station can vary from time to time.
In many local area networks, stations can be easily added to, removed from, and moved from place to place within the network. While there are numerous local area networks presently known, they can be classified into two general types. The first type of network is referred to as a "centralized network" which is characterized by the requirement of a centralized network controller which implements the network protocol. The second type of local area network is referred to as a "distributed network" which does not require a centralized network controller, and instead provides each station within the network with a communication controller having a medium access control (MAC) unit that locally implements the network protocol within each communication controller.
In a distributed local area network, packet switching is a technique commonly employed to dynamically allocate the communication resources of the network among multiple communicating stations. According to this technique, messages to be communicated between stations are partitioned (by the transmitting station's processor) into packets, having a fixed maximum size. The packets are then ascribed a station (i.e. source) identifier. The packets are then placed on the communication medium by the station's communication controller. Such packets are then sensed and selectively processed by the communication controller of the destination station in the network.
Any packet from one station to another station contains various fields of information specified in accordance with a predetermined network protocol. The information typically includes the identity of the source station, the identity of the destination station, and various other information concerning the characteristics of the packet. In some network protocols, a number of different types of packets may appear on the communication medium in accordance with the network protocol. Typically, these packets relate to either communication control or data-transfer functions.
To more fully appreciate the problems associated with conventional communication controllers used in the stations of distributed local-area-networks, reference is made to FIGS. 1 through 3.
In FIG. 1, a distributed local area-network 1 is shown, comprising a plurality of stations (i.e. nodes A through H) which are operably associated to a communication medium 2, such as a cable while a number of network configurations are possible, a token-ring configuration is schematically illustrated for purposes of illustration. In FIG. 1A, each station is shown to generally comprise a host processor (e.g., CPU) 3, a program memory 4, a system memory 5, a communication controller 6, a system bus 7, and a communication medium interface unit 8. The processor, program memory and system memory are each associated with a system bus 7, and the system bus, in turn, is interfaced with communication controller 6, as shown. The communication controller is interfaced with the communication medium by way of the communication medium interface unit. Typically, the communication medium interface unit is suitably adapted for the particular characteristics of the communication medium being employed in the network.
In general, communications controllers, and LAN controllers in particular, are usually integrated into a system architecture and software environment by providing the means for supporting two independent data queues in software: a transmit queue and a receive queue. Each queue is associated with a process, namely, the transmit process and the receive process of the low-level software communications driver.
The transmit queue holds the elements that the software intends to transmit. In a packet-switched environment of a local area network, these elements are usually data packets that include a block of data to be transmitted and some associated information like the destination for the block of data. The receive queue hold the elements that the station has received, again usually packets with a block of data and associated information such as the sender of the data block.
Elements are added to the transmit queue by the software driver whenever it needs to transmit information. Elements are removed from the transmit queue after successful transmission is assumed. Removal of the elements can be done either by the low-level software driver or by the communications controller. Elements are added to the receive queue by the communications controller whenever a relevant packet is received, and are removed by the low-level software driver upon processing the packet.
The transmit and receive queues are managed by software in system memory, eventually meet the communication controller. The interface between the queues and the communications controller determines the behavior of the queues during the addition of receive elements and removal of transmit elements.
Management of the transmit and receive queue elements at the level of the communication controller has been attempted in a variety of ways.
For example, some prior art communication controllers are as simple as a single element queue, in which the controller can handle only one transmit and one receive element at a time and the host processor must be involved in feeding the queue. Representative of this type of prior art is the 90C65 Communication Controller from Standard Microsystems Corporation of Hauppauge, N.Y. A major shortcoming of this type of communication controller is that it is highly sensitive to interrupt latency of the host processor.
An alternative type of prior art communication controller employs queues for transmit and receive commands while storing corresponding data packets in a randomly accessible memory associated with the communication controller. Representative of this type of prior art is the 90C66 Communication Controller from Standard Microsystems. Advantageously, this communication controller design is substantially less sensitive to interrupt latency in comparison with the above-described communication controller.
Using an altogether different technique than the command queuing scheme described above, the prior art has sought to extend the transmit and receive data queues into the communication controller by simulating transmit and receive data queues in the data packet buffer memory of the communication controller. In general, there have been several different approaches to implementing this generalized memory management technique.
For example, according to one approach, many transmit and receive data elements can be managed as a "ring buffer," in which data packet buffer memory is configured as a number of memory elements which can be sequentially allocated and accessed. Prior art representative of this approach includes the 8390 NIC Communication Controller from National Semiconductor Corporation, and the Etherstar.RTM. Ethernet Communications Controller from Fujitsu Corporation. Significant shortcomings and drawbacks of the "ring buffer" communication controller are inefficient memory utilization, high CPU overhead and memory fragmentation.
According to an alternative approach for simulating transmit and receive data queues at the communication controller level, a disjointed array of memory storage locations are linked together with the use of address pointers compiled in accordance with a "linked list". The major subcomponents of such a conventional "linked-list" data communication controller 6 are shown in FIG. 1B. In general, communication controller 6 comprises a CPU interface unit 9, a linked-list processor 10, a medium access control (MAC) unit 11, and a MAC interface unit 12. Associated with the controller is a data packet buffer memory (RAM) 13. The CPU interface unit interfaces system bus 7 with linked-list processor 10 and data packet memory buffer 13 by way of an address and data bus, as shown. The MAC interface unit interfaces medium access control unit 11 with the link-list processor and the data packet buffer memory, also by way of an address and data bus, as shown. Prior art representative of the above type device includes the TMS380 Communication Controller from Texas Instrument Corporation.
In order for the linked-list communication controller to find the memory storage location where a packet begins, as well as the storage locations where each one of the buffers (comprising a packet) begins, the software driver must perform a number of computations. Such packet address computations and the necessity of managing numerous address pointers create high software overhead. Also with this prior art approach, memory utilization is inefficient owing to the fact that pointers and linked-list structures utilize memory and because linked-lists use fixed memory allocations between transmit and receive queues.
In communication networks utilizing multiple layer communication protocols, such as the IEEE 802.5 Standard, the processing requirements of the data communication controller becomes substantially greater than when using the Arcnet, Ethernet or other single packet-type communication protocols. Specifically, the IEEE 802.5 standard, the media access control (MAC) layer protocol requires that MAC layer data packets be internally captured and processed within the data communication controller, while higher layer protocol (i.e. Non-MAC) packets are efficiently transferred to and from the associated host system for processing according to the higher layer protocol.
In communication networks utilizing multi-layer communication protocols it is a common practice to use a communication processor chip which includes a single CPU, a serial communication subsystem and a bus interface unit with a DMA controller. Associated with the communication processor chip and the host system is shared memory, referred to as adaptor RAM. Single chip communication processors using this type of architecture have been produced in the market and are described in various technical journals, e.g. "A 16-Mbit/s Adapter Chip for the IBM Token-Ring Local Area Network" by J. D. Blair, et al. in IEEE Journal of Solid-State Circuits, Vol. 24, No. 6, December 1989. One major drawback of this architecture is that the CPU in the chip handles both the MAC layer protocol and the management of host commands and transmit and receive (15.queue) buffers, thereby overloading the single CPU with too many tasks and increasing the latency of the CPU's task switching. Another drawback of this prior art design is that the CPU uses the same datapath to fetch program instructions and to execute instructions involving other data transferring units inside the communication processor chip. Naturally, this creates a bottleneck for CPU processing throughput. In such prior art designs, data transfer over the single datapath typically includes CPU program instruction fetch; CPU instruction execution; transfer of transmit packet data from the attached host memory to the adapter RAM; transfer of transmit packet data from the adapter RAM to the serial communication subsystem unit; transfer of received packet data from the serial communication subsystem unit to the adapter RAM; and transfer of received packet data from the adapter RAM to attached host system memory.
Another single chip communication processor architecture has been described in "VLSI Architecture for IEEE 802.5 Token-Ring LAN Controller" by Koichi Tanaka, et al., in The Proceedings of IEEE 1989 Custom Integrated Circuits Conference. The chip comprises of a single CPU, a state-machine DMA controller with three DMA channels, and a serial communication subsystem. An major drawback of this architecture is that the CPU is responsible for (i) handling all the host commands; (ii) starting and ending transmit and receive packets (even for Non-MAC packets destined for the host); (iii) communicating with the DMA controller to transfer packet data to and from the attached host memory; and (iv) processing MAC protocol packets. While this architecture demands high throughput from the single CPU, the CPU's access to the working FIFO/RAM memory for packet processing is greatly hindered by the need of the serial communication subsystem to access the FIFO/RAM memory using the same data bus. Naturally, this reduces the execution speed of the CPU. In 16 Mbs Token-Ring environments, 2 Mhz bus bandwidth is used by the serial communication subsystem alone, thus leaving only 2 Mhz bandwidth for the CPU instruction execution.
Thus, there is a great need in the art for a data communicating processing device capable of internally separating protocol-layer dependent data packets, and having independent data paths and multiple central processing units for internally processing data packets associated with one layer of communication protocol, while efficiently transferring data packets associated with other communication protocol-layers, to the host system.